The complexity of distributed edge coloring depends heavily on the palettesize as a function of the maximum degree $\Delta$. In this paper we explore thecomplexity of edge coloring in the LOCAL model in different palette sizeregimes. 1. We simplify the \emph{round elimination} technique of Brandt et al. andprove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees.The simplified technique is based on two ideas: the notion of an irregularrunning time and some general observations that transform weak lower boundsinto stronger ones. 2. We give a randomized edge coloring algorithm that can use palette sizes assmall as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier forrandomized approaches. The running time of the algorithm is at most$O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of apermissive version of the constructive Lovasz local lemma. 3. We develop a new distributed Lovasz local lemma algorithm fortree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-edgecoloring algorithm for trees running in $O(\log\log n)$ time. This algorithmarises from two new results: a deterministic $O(\log n)$-time LLL algorithm fortree-structured instances, and a randomized $O(\log\log n)$-time graphshattering method for breaking the dependency graph into independent $O(\logn)$-size LLL instances. 4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing'stheorem) is to extend partial colorings by iteratively re-coloring parts of thegraph. We prove that this approach may be viable, but in the worst caserequires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This standsin contrast to distributed algorithms for Brooks' theorem, which exploit theexistence of $O(\log_\Delta n)$-length augmenting paths.
展开▼
